#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>

#include "Sorter.h"

using namespace std;

Sorter::Sorter(SortType type)
{
	_sort_type = type;
}

/* Refrenced from Design and Analysis of Algorithms
* Merge Sort - pg 126
*/
void Sorter::merge_arrs(Edge *B, int p, Edge *C, int q, Edge *A)
{  
	register int i, j, k;
	i = j = k = 0;
	
	while(i < p && j < q)
	{
		// compare costs of edges
		if(B[i].cost <= C[j].cost)
		{
			// swap
			A[k] = B[i];
			i++;
		}
		else
		{
			// swap
			A[k] = C[j];
			j++;
		}			
		k++;
	}
	
	if (i == p)
	{
		// Copy C[j..q] to A[k..p+q]
		for (int a = j, b = 0; a < q; a++, b++)
			A[k + b] = C[a];
	}
	else
	{
		//Copy B[i..p] to A[k..p+q]
		for (int a = i, b = 0; a < p; a++, b++)
			A[k + b] = B[a];	
	}

}

/* Refrenced from Design and Analysis of Algorithms
* Merge Sort - pg 126
*/
void Sorter::merge_sort(Edge *A, int size)
{
    if (size > 1)
	{
		register int i, j;
		Edge *B, *C;		
		
		int bSize = (int) floor((float) size / 2);		
		B = new Edge[bSize];	
		// Copy A[0..floor(n/2)-1] to B[0..floor(n/2)-1]
		for (i = 0; i < bSize; i++)
			B[i] = A[i];		
		
		int cSize = (int) ceil((float) size / 2); 		
		C = new Edge[cSize];
		//Copy A[floor(n/2)..n-1] to C[0..ceil(n/2)-1]
		for (j =0; i < size; i++, j++)
			C[j] = A[i];		
		
		merge_sort(B, bSize);
		merge_sort(C, cSize);
		merge_arrs(B, bSize, C, cSize, A);
		
		delete[] B;
		delete[] C;
	}	
}

/* Refrenced from Design and Analysis of Algorithms
* Bubble Sort - pg 100
*/
void Sorter::bubble_sort(Edge *arr, int size)
{
	register int i, j;

	for(i = 1; i < size; i++) 	
		for(j = size - 1; j >= i; j--) 		
			if (arr[j-1].cost > arr[j].cost) 
				// if out of order exhange elements
				std::swap(arr[j-1],arr[j]);		
	
}			

Edge* Sorter::sort(Edge *edgeArray, int size)// or Edge **sort(Edge **edgeArray, int size); if you prefer
{
			
	//display original array
	//cout << "Original array is:\n   ";
	//for(i=0; i<size; i++) std::cout << edgeArray[i].cost << endl;
	
	switch (_sort_type)
	{
		case Sorter::heap :
			heap_sort(edgeArray, size);
			break;
			
		case Sorter::merge : 
			merge_sort(edgeArray, size);
			break;
			
		case Sorter::bubble :
			bubble_sort(edgeArray, size);			
			break;		
	}		
					
	//display sorted array
	/*
	cout << "\nSorted array is:\n";
	int count = 0;
	for(int i=0; i<size; i++) 
		count++,cout << edgeArray[i].cost << endl;
	cout << "Count: " << count << endl;;
	*/
	return edgeArray;
}	


/* Refrenced from wikipedia
* http://en.wikipedia.org/wiki/Heapsort
*/
void Sorter::heap_sort(Edge *arr, int size)
{
	// place in max heap order
	heapify(arr, size);
	
	int e = size - 1;
	while (e > 0)
	{
		// swap root with last element
		std::swap(arr[e] , arr[0]);
		// put heap in max heap order
		sift_down(arr, 0, e - 1);
		e--;	
	}
	
}

void Sorter::heapify(Edge *arr, int size)
{
	// [][][][P]|[][][][C][C]
	
	// assign index of last parent node
	int s = size / 2 - 1;
	
	while (s >= 0)
	{
		// sift down the node into its appropriate place
		sift_down(arr, s, size - 1);
		s--;	
	}

}

void Sorter::sift_down(Edge *arr, int start, int end)
{
	int r = start;	

	// while until one child is left
	while (r * 2 + 1 <= end)
	{
		// get first child
		int c = r * 2 + 1;
		int s = r;
		
		// if root smaller than left child
		if (arr[s].cost < arr[c].cost)
			s = c;
		
		// if right child exists and if its bigger 
		// than what was current swapped
		if (c + 1 <= end && arr[s].cost < arr[c + 1].cost)
			s = c + 1;
		
		// does any swapping need to be done
		if (s != r)
		{
			// swap nodes
			std::swap(arr[r], arr[s]);
			// repeat sifting down the child
			r = s;
		}
		else
			return;
	
	}
}